package net.tp.struct.tree;

import java.util.*;
import java.util.function.*;
import java.lang.reflect.*;
import net.tp.struct.bst.*;
import net.tp.util.*;
import net.tp.struct.*;
import java.util.concurrent.atomic.*;
import static net.tp.util.Utils.*;

/**
 * Build tree from its traversal or its text presentation.
 *
 * Some common binary tree traversals are: pre-order, in-order, post-order and level-order traversals. Each traversal alone cannot identify the tree. In-order traversal combined with any other traversal can identify the tree. Pre-order combined with post-order cannot uniquely identify a tree. They can reconstruct the tree but for one-leaf node, it cannot determine if the leaf is the right or left child.
 *
 * @author Trung Phan
 *
 */
public class TreeBuilder {

    /**
     * Build Binary Tree from preorder and inorder arrays.
     *
     * This is a recursive version.
     *
     * <pre>
     *      4      
     *    ┌─┴──┐   
     *    3    5   
     *   ┌┴─┐ ┌┴─┐ 
     *   1       7 
     *  ┌┴┐     ┌┴┐
     *  0 2     6 8
     *
     *  pre order: 4 3 1 0 2 5 7 6 8
     *  in order : 0 1 2 3 4 5 6 7 8 S
     * </pre>
     * <p>Every recursive call will build the sub tree given the pre-order and in-order list of that subtree. The first item of te pre-order is the root of the tree, the in-order list will tell how to divide the subtree into the left subtree and the right subtree. A naive approach would be to find the position of the root value within the in-order list to divide the list into left and right. This would take $O(n^2)$ time:</p>
     * <pre>
     *  function buildSubtree(N: subtree size, pre-order list, in-order list): sub tree root
     *      root = pre-order[0]
     *      pos = find position of root in in-order list: O(N) time
     *
     *      if pos == 0 then root.left = null
     *      else root.left = buildSubtree(pos, pre-order[1:], in-order)
     *
     *      if pos == N-1 then root.right = null
     *      else root.right = buildSubtree(N - pos, pre-order[pos+1:], in-order[pos+1:])
     *
     *      return root
     * </pre>
     *
     * <p>To make the running time, we can figure out the subtree size dynamically. In fact, we only need to know where the subtree end in the in-order list. We will turn the pre-order and in-order into a queue or stack and will remove the items out of the queue until they are empty. It does not matter whether it's queue or stack as we only remove the head iteam.</p>
     * <pre>
     *  # input:  pre-order queue for the subtree (without knowing where it ends)
     *            in-order queue for the sub tree (which will end at element end exclusive)
     *
     *  # post state: 
     *            In-order queue elements are popped til the end (i.e. in-order.head == end).
     *            Let N be the number of elements removed: N = subtree size.
     *            N elements are removed from the pre-order tree. So basically, all the
     *            elements for the subtree will be removed from in-order and pre-order queue.
     *
     *  # output: sub tree root
     *
     *  # assume: n is subtree size, p: left subtree size, q = n-1-p: right subtree size
     *
     *  function buildSubtree(pre-order queue, in-order queue, end): sub tree root
     *      root = pre-order.removeHead() # 1 element is removed from pre-order
     *
     *      if in-order.head == root then there is no left tree (i.e. p = 0)
     *      else root.left = buildSubtree(queue, in-order, root)
     *
     *      # At this point, p elements are removed until in-order.head == root.
     *      # Additional p elements are removed from the pre-order queue.
     *
     *      in-order.removeHead() # 1 element is removed from in-order
     *
     *      # At this point, p+1 elements are removed from in-order and pre-order queue,
     *      # leaving q elements for the right subtree
     *
     *      if in-order.head == end then there is no right tree (i.e. q = 0)
     *      else root.right = buildSubtree(queue, in-order, end)
     *
     *      # At this point, all the elements of the right tree are removed from in-order
     *      # and pre-order queue, making in-order.head == end, which satisfy the post state
     *
     *      return root
     * </pre>
     *
     * @param <N> node type
     * @param nodeClass node class
     * @param preOrders preorder
     * @param inOrders inOrder
     * @return binary tree's root
     * @time $O(n)$
     * @space $O(n)$
     */
    public static <N extends AbstractBinNode<N>> N buildBinTreeFromPreIn(Class<N> nodeClass, List<String> preOrders, List<String> inOrders) {

        if (preOrders.size() != inOrders.size()) throw new IllegalArgumentException();
        if (preOrders.size() == 0) return null;

        return buildSubTreeRecursive(nodeClass, null, new SeqReader<>(preOrders), new SeqReader<>(inOrders));
    }

    private static <N extends AbstractBinNode<N>> N buildSubTreeRecursive(Class<N> nodeClass, String to, SeqReader<String> preOrders, SeqReader<String> inOrders) {
        assert preOrders.hasNext() : "preOrders cannot be empty";
        assert inOrders.hasNext() : "inOrders cannot be empty";
    
        String rootValue = preOrders.next();
        N root = cast(newNode(nodeClass, rootValue));

        if (!inOrders.peek().equals(rootValue))
            root.bindLeft(buildSubTreeRecursive(nodeClass, rootValue, preOrders, inOrders));

        assert inOrders.peek().equals(rootValue);
        inOrders.next();

        if (inOrders.hasNext() && !inOrders.peek().equals(to))
            root.bindRight(buildSubTreeRecursive(nodeClass, to, preOrders, inOrders));

        assert !inOrders.hasNext() || inOrders.peek().equals(to);

        return root;
    }

    /**
     * Build Binary Tree from postorder and inorder arrays.
     * Basically this ultilize the recursive version of build sub tree from pre-order and in-order list. The trick is to reverse the order of the post-order and in-order lists. Then reverse the children of every node in the output.
     *
     * @param <N> node type
     * @param nodeClass node class
     * @param postOrders preorder
     * @param inOrders inOrder
     * @return binary tree's root
     */
    public static <N extends AbstractBinNode<N>> N buildBinTreeFromPostIn(Class<N> nodeClass, List<String> postOrders, List<String> inOrders) {

        if (postOrders.size() != inOrders.size()) throw new IllegalArgumentException();
        if (postOrders.size() == 0) return null;

        N root = buildSubTreeRecursive(nodeClass, null, 
                new SeqReader<>(new LinkedList<>(postOrders).descendingIterator()),
                new SeqReader<>(new LinkedList<>(inOrders).descendingIterator()));

        TreeTraversal.preOrder(root, (n) -> {
            N tmp = n.left;
            n.left = n.right;
            n.right = tmp;
        });

        return root;
    }

    /**
     * Build binary tree from pre-order and in-order list.
     *
     * This is a non-recursive approach.
     *
     *
     * @param <N> node type
     * @param nodeClass node class
     * @param preOrders pre-order list
     * @param inOrders in-order list
     * @return binary tree
     * @time $O(n)$
     * @space $O(1)$
     * @see <p>Construction of a Tree from its Traversals in Optimal Time and Space</p>
     */
    public static <N extends AbstractBinNode<N>> N buildBinTreeFromPreInNonRecursive(Class<N> nodeClass, List<String> preOrders, List<String> inOrders) {

        if (preOrders.size() != inOrders.size()) throw new IllegalArgumentException();
        if (preOrders.size() == 0) return null;

        preOrders = new LinkedList<>(preOrders);
        inOrders = new LinkedList<>(inOrders);

        Map<String, N> str2N = new HashMap<>();

        N current, root, rightAncestor;

        String currentValue = preOrders.remove(0);
        current = root = cast(newNode(nodeClass, currentValue));
        str2N.put(currentValue, current);
        rightAncestor = null;

        while (!inOrders.isEmpty()) {
            if (current != str2N.get(inOrders.get(0))) {
                rightAncestor = current;
                currentValue = preOrders.remove(0);
                current.bindLeft(cast(newNode(nodeClass, currentValue)));
                current = current.left; // move current down the sub tree
                str2N.put(currentValue, current);
                current.right = rightAncestor; // thread link
            }
            else {
                inOrders.remove(0);
                if (!inOrders.isEmpty() &&
                    (current.right == null || current.right != str2N.get(inOrders.get(0)))) {

                    rightAncestor = current.right;
                    currentValue = preOrders.remove(0);
                    current.bindRight(cast(newNode(nodeClass, currentValue)));
                    current = current.right; // move current down the sub tree
                    str2N.put(currentValue, current);
                    current.right = rightAncestor; // thread link
                }
                else {
                    rightAncestor = current.right;
                    current.bindRight(null);
                    current = rightAncestor; // move current through the thread link
                }
            }
        }

        return root;
    }

    public static <N extends AbstractBinNode<N>> N buildTree(Class<?> nodeClass, String ... drawLines) {
        return buildTree(nodeClass, AbstractBinNode<N>::bindChildren, drawLines);
    }

    /**
     * Build tree (binary tree or n-ary tree) from text presentation.
     *
     * <p>The tree presentation looks like this:</p>
     * <pre>
     *      4      
     *    ┌─┴──┐   
     *    3    5   
     *   ┌┴─┐ ┌┴─┐ 
     *   1       7 
     *  ┌┴┐     ┌┴┐
     *  0 2     6 8
     * </pre>
     *
     * @param <N> node class
     * @param nodeClass class of the node
     * @param bindChildrenFunc function to bind children to a node
     * @param drawLines text presetnation of the tree.
     * @return tree's root
     */
    public static <N> N buildTree(Class<?> nodeClass,
            BiConsumer<N, Iterable<N>> bindChildrenFunc, 
            String... drawLines) {

        if (drawLines.length == 0) return null;

        int rootPos = findNode(drawLines[0], 0);

        return buildSubtreeAtPosAndLine(nodeClass, bindChildrenFunc, drawLines, 0, rootPos);
    }

    private static Object newNode(Class<?> nodeClass, String values) {
        if (values.length() == 0) return null;

        String[] _params = values.split(":");
        Object[] params = new Object[_params.length];
        for (int i = 0; i < params.length; i++) params[i] = guessValue(_params[i]);
        for (Constructor<?> constructor : nodeClass.getConstructors()) {
            Class<?>[] types = constructor.getParameterTypes();
            if (params.length == types.length) {
                try {
                    return constructor.newInstance(params);
                } catch (InstantiationException | IllegalAccessException | InvocationTargetException e) {
                    throw new IllegalStateException(e);
                }
            }
        }
        throw new IllegalStateException("Cannot create instance of " + nodeClass);
    }

    /**
     * Return value as Integer, Double or String.
     * @param value string value
     * @return Integer, Double or String value
     */
    private static Object guessValue(String value) {
        try { return Integer.parseInt(value); }
        catch (NumberFormatException e) {
            try { return Double.parseDouble(value); }
            catch (NumberFormatException e2) { return value; }
        }
    }

    /**
     * Build subtree given the root lies at given line and position.
     * 
     * @param <N> node type
     * @param nodeClass node class to instantiate a new node
     * @param bindChildrenFunc bindChildren function: function to assign children to a node
     * @param drawLines text representation of the tree
     * @param line line number of the root
     * @param pos position of the root
     */
    private static <N> N buildSubtreeAtPosAndLine(Class<?> nodeClass, BiConsumer<N, Iterable<N>> bindChildrenFunc, String[] drawLines, int line, int pos) {
            
        N node = cast(newNode(nodeClass, getNode(drawLines[line], pos)));
        if (node != null && line < drawLines.length - 1) {
            List<Integer> children = getChildren(drawLines[line], drawLines[line+1], pos);
            if (children.size() == 2) {
                N left = buildSubtreeAtPosAndLine(nodeClass, bindChildrenFunc, drawLines, line+2, children.get(0));
                N right = buildSubtreeAtPosAndLine(nodeClass, bindChildrenFunc, drawLines, line+2, children.get(1));
                bindChildrenFunc.accept(node, Wrappers.makeIterable(left, right));
            }
        }
        return node;
    }

    static int findNode(String line, int fromPos) {
        while (fromPos < line.length() && line.charAt(fromPos) == ' ') {
            fromPos++;
        }
        return fromPos == line.length() ? -1 : fromPos;
    }

    static String getNode(String line, int atPos) {
        if (atPos == -1 || line.charAt(atPos) == ' ') return "";
        int from = atPos;
        int to = atPos + 1;
        while (from > 0 && line.charAt(from-1) != ' ') from--;
        while (to < line.length() && line.charAt(to) != ' ') to++;
        return line.substring(from, to);
    }

    private static final String EDGE_CHARS = "┌┐┬┼├┤";

    static List<Integer> getChildren(String lineParent, String lineEdge, int atPos) {

        if (lineParent.charAt(atPos) == ' ')
            throw new IllegalArgumentException();
        while (atPos > 0 && lineParent.charAt(atPos-1) != ' ') atPos--;

        int childPos = atPos;
        while (childPos < lineEdge.length() && lineEdge.charAt(childPos) == ' '
                && childPos < lineParent.length() && lineParent.charAt(childPos) != ' ')
            childPos++;

        if (childPos == lineParent.length() || lineParent.charAt(childPos) == ' ')
            return Collections.emptyList();
        
        while (childPos > 0 && lineEdge.charAt(childPos-1) != ' ') childPos --;

        List<Integer> children = new ArrayList<>();
        for (; childPos < lineEdge.length() && lineEdge.charAt(childPos) != ' '; childPos++) {
            if (EDGE_CHARS.indexOf(lineEdge.charAt(childPos)) > -1)
                children.add(childPos);
        }

        return children;
    }
}
